#include <bits/stdc++.h>
using namespace std;

#define S64 signed long long
#define MAX_N 1000086
#define BASEN 29

S64 pwr[MAX_N] = {1}, h2[MAX_N], h1;
char s1[MAX_N], s2[MAX_N];

int main() {
   int t, ans;
   scanf("%d", &t);
   for (int i = 1; i < MAX_N; i++) pwr[i] = pwr[i - 1] * BASEN;
   while (t--) {
      scanf("%s%s", s1, s2);
      int l1 = strlen(s1), l2 = strlen(s2), ans = 0;
      h1 = 0;
      for (int i = 0; i < l1; i++) h1 = h1 * BASEN + s1[i] - 'A' + 1;
      h2[0] = 0;
      for (int i = 1; i <= l2; i++) h2[i] = h2[i - 1] * BASEN + s2[i - 1] - 'A' + 1;
      for (int i = 0; i <= l2 - l1; i++)
         if (h1 == h2[i + l1] - h2[i] * pwr[l1]) ans++;
      printf("%d\n", ans);
   }
   return 0;
}
